/**
 * 
 */
package name.marz.to.go.btree.node;

/**
 * @author masaru-gotou
 *
 */
public class ArrayNode extends AbstractNode {
	private Key keys[];
	private Object pointers[];
	
	ArrayNode() {
		// NOP
	}
	
	ArrayNode(int keycount) {
		keys = new Key[keycount];
		pointers = new Object[keycount];
	}
	
	
	/**
	 * Nodeの中味をクリアする
	 */
	@Override
	public void clear() {
		leftPointer = null;
		for ( int i=0; i<keys.length; i++ ) {
			keys[i] = null;
			pointers[i] = null;
		}
	}
	
	/* (non-Javadoc)
	 * @see btree.node.Node#size()
	 */
	public int getMaxKeys() {
		return keys.length;
	}
	@Override
	public void setMaxKeys(int keycount) {
		keys = new Key[keycount];
		pointers = new Object[keycount];
	}
	/* (non-Javadoc)
	 * @see btree.node.Node#getKeyCount()
	 */
	public int getKeyCount() {
		for ( int i = 0; i<keys.length; i++ ) {
			if ( keys[i] == null ) {
				return i;
			}
		}
		return keys.length;
	}
	void setKeyCount(int keycount) {
		keys = new Key[keycount];
		pointers = new Object[keycount];
	}
	
	/* (non-Javadoc)
	 * @see btree.node.Node#getPointer(btree.node.Key)
	 */
	public Object getPointer(Key key) {
		for ( int i=keys.length-1; i>=0; i-- ) {
			if ( keys[i] != null ) {
				if ( key.compareTo(keys[i]) >= 0 ) {
					return pointers[i];
				}
			}
		}
		return leftPointer;
	}
	/* (non-Javadoc)
	 * @see btree.node.Node#getPointer(int)
	 */
	public Object getPointer(int index) {
		return pointers[index];
	}
	/* (non-Javadoc)
	 * @see btree.node.Node#getKey(int)
	 */
	public Key getKey(int index) {
		return keys[index];
	}
	private void setKey(int index,Key key) {
		keys[index] = key == null ? null : (Key)key.clone();
	}
	private void setPointer(int index,Object p) {
		pointers[index] = p;
	}
	
	/**
	 * キー値を追加する
	 * 重複を許可する
	 * @param key
	 * @param pointer
	 * @throws NodeOverflowException	ノードが溢れたときスローされる
	 */
	@Override
	public void add(Key key, Object pointer) throws NodeOverflowException {
		int empty = -1;
		// 空きを探す（後ろから）
		for ( int i=keys.length-1; i>=0; i-- ) {
			if ( keys[i] == null ) {
				empty = i;
				break;
			}
		}
		// 空きが無ければ例外スロー
		if ( empty == -1 ) throw new NodeOverflowException();
		// 空きがあれば順列に並べて追加
		keys[empty] = key == null ? null : (Key) key.clone();
		pointers[empty] = pointer;
		sort();
	}
	
	/* (non-Javadoc)
	 * @see btree.node.Node#isLeaf()
	 */
	public boolean isLeaf() {
		for ( int i=0; i<keys.length; i++ ) {
			if ( pointers[i] != null && pointers[i] instanceof ArrayNode ) {
				return false;
			}
		}
		return true;
	}
	
	/* (non-Javadoc)
	 * @see btree.node.Node#hasKey(btree.node.Key)
	 */
	public boolean hasKey(Key key) {
		for ( int i=0; i<keys.length; i++ ) {
			if ( keys[i] != null ) {
				if ( keys[i].compareTo(key) == 0 ) return true;
			}
		}
		return false;
	}

	/**
	 * キーとポインタをソートする
	 */
	private void sort() {
		for (int i = 0; i < keys.length; i++) {
			for (int j = 1; j < keys.length-i; j++) {
				// j-1==data j==null : no swap
				// j-1==data j==data : compare & swap
				// j-1==null j==null : no swap
				// j-1==null j==data : swap
				if ( keys[j-1] != null ) {
					if ( keys[j] != null ) {
						if ( keys[j].compareTo(keys[j-1]) < 0 ) {
							swap(j-1,j);
						}
					}
				} else {
					if ( keys[j] != null ) {
						swap(j-1,j);
					}
				}
			}
		}
	}

	private void swap(int i, int j) {
		Key tmpk = keys[i];
		Object tmpp = pointers[i];
		keys[i] = keys[j];
		pointers[i] = pointers[j];
		keys[j] = tmpk;
		pointers[j] = tmpp;
		
	}

	/* (non-Javadoc)
	 * @see btree.node.Node#getFirstKey()
	 */
	public Key getFirstKey() {
		return keys[0];
	}

//	/* (non-Javadoc)
//	 * @see btree.node.AbstractNode#newNode()
//	 */
//	@Override
//	public Node newNode() {
//		ArrayNode obj = new ArrayNode(keys.length);
//		obj.clear();
//		return obj;
//	}

	@Override
	public void remove(Key key) {
		for ( int i=0; i<keys.length; i++ ) {
			if ( keys[i] != null ) {
				if( keys[i].equals(key) ) {
					keys[i] = null;
					pointers[i] = null;
				}
			}
		}
	}

	@Override
	public Node split() {
		ArrayNode node = this;
		int keycount = node.getKeyCount();
//		ArrayNode larger_node = (ArrayNode)node.newNode();
		ArrayNode larger_node = (ArrayNode)NodeFactory.createNode(node.getClass().getName(), node.getMaxKeys());
		// 後半のキーを新しいノードに移す
		for ( int i=keycount/2,j=0; i<keycount; i++,j++ ) {
			larger_node.setKey(j,node.getKey(i));
			larger_node.setPointer(j, node.getPointer(i));
			// 移された側はクリアする
			node.setKey(i,null);
			node.setPointer(i, null);
		}
		return larger_node;
	}

	@Override
	public Object clone() {
		// 新しいインスタンスを作成
		ArrayNode n = (ArrayNode)NodeFactory.createNode(ArrayNode.class.getName(), keys.length);
		// キー値をコピー
		System.arraycopy(this.keys, 0, n.keys, 0, this.keys.length);
		// 左側のポインタの先を複製
		if ( this.leftPointer instanceof ArrayNode ) {
			n.leftPointer = ((ArrayNode)this.leftPointer).clone();
		} else {
			n.leftPointer = this.leftPointer;
		}
		// その他のポインタの先を複製
		for ( int i=0; i < pointers.length; i++ ) {
			if ( this.pointers[i] instanceof ArrayNode ) {
				n.pointers[i] = ((ArrayNode)this.pointers[i]).clone();
			} else {
				n.pointers[i] = this.pointers[i];
			}
		}
		return n;
	}

//	@Override
//	public NodeMemento save() {
//		NodeMemento m = new NodeMemento(this);
//		return m;
//	}
//
//	@Override
//	public void restore(NodeMemento m) {
//		keys = null;
//		pointers = null; 
//		
//	}

}
